
template <typename T>
void insertion_sort(T a[], size_t size)
{
    for (size_t i = 1; i < size; i++)
    {
        T value = a[i];

        size_t j = i;
        while (j > 0 && a[j - 1] > value)
        {
            a[j] = a[j - 1];
            j--;
        }

        if (j < i)
        {
            a[j] = value;
        }
    }
}
